package main

import (
	"fmt"
	"math/rand"
	"time"
)

const MaxLevel = 16 // 定义跳表的最大层数

// Node 定义跳表中的节点结构
type Node struct {
	value int     // 节点存储的值
	next  []*Node // 指向每一层的下一个节点
}

// SkipList 定义跳表结构
type SkipList struct {
	head  *Node // 头节点
	level int   // 当前跳表的实际层数
}

// NewNode 创建一个新的节点
func NewNode(value int, level int) *Node {
	return &Node{
		value: value,
		next:  make([]*Node, level), // 初始化节点的 next 数组
	}
}

// NewSkipList 创建一个新的跳表
func NewSkipList() *SkipList {
	return &SkipList{
		head:  NewNode(0, MaxLevel), // 头节点的值为 0，层数为 MaxLevel
		level: 1,                    // 初始层数为 1
	}
}

// randomLevel 随机生成一个层数
func (list *SkipList) randomLevel() int {
	level := 1
	// 以 50% 的概率增加一层，直到达到最大层数
	for rand.Int()%2 == 1 && level < MaxLevel {
		level++
	}
	return level
}

// Insert 在跳表中插入一个新值
func (list *SkipList) Insert(value int) {
	update := make([]*Node, MaxLevel) // 记录每一层需要更新的节点
	current := list.head              // 从头节点开始

	// 从最高层开始遍历，找到每一层需要更新的位置
	for i := list.level - 1; i >= 0; i-- {
		for current.next[i] != nil && current.next[i].value < value {
			current = current.next[i]
		}
		update[i] = current
	}

	current = current.next[0] // 移动到第 0 层

	// 如果当前节点为空或值不等于要插入的值，则插入新节点
	if current == nil || current.value != value {
		newLevel := list.randomLevel() // 随机生成新节点的层数

		// 如果新节点的层数大于当前跳表的层数，则更新头节点的 next 数组
		if newLevel > list.level {
			for i := list.level; i < newLevel; i++ {
				update[i] = list.head
			}
			list.level = newLevel
		}

		newNode := NewNode(value, newLevel) // 创建新节点
		// 更新每一层的 next 数组
		for i := 0; i < newLevel; i++ {
			newNode.next[i] = update[i].next[i]
			update[i].next[i] = newNode
		}
		fmt.Printf("Inserted: %d\n", value)
	} else {
		fmt.Printf("Value already exists: %d\n", value)
	}
}
// Search 在跳表中搜索一个值
func (list *SkipList) Search(value int) bool {
	current := list.head // 从头节点开始

	// 从最高层开始遍历，找到每一层小于目标值的最大节点
	for i := list.level - 1; i >= 0; i-- {
		// 移动到下一层
		for current.next[i] != nil && current.next[i].value < value {
			current = current.next[i]
		}

		// 提前检查当前层的下一个节点是否为目标值
		if current.next[i] != nil && current.next[i].value == value {
			return true
		}
	}

	// 如果在所有层中都没有找到目标值，返回 false
	return false
}

// Delete 从跳表中删除一个值
func (list *SkipList) Delete(value int) {
	update := make([]*Node, MaxLevel) // 记录每一层需要更新的节点
	current := list.head              // 从头节点开始

	// 从最高层开始遍历，找到每一层小于目标值的最大节点
	for i := list.level - 1; i >= 0; i-- {
		for current.next[i] != nil && current.next[i].value < value {
			current = current.next[i]
		}
		update[i] = current
	}

	current = current.next[0] // 移动到第 0 层

	// 如果当前节点为目标值，则删除该节点
	if current != nil && current.value == value {
		for i := 0; i < list.level; i++ {
			if update[i].next[i] != current {
				break
			}
			update[i].next[i] = current.next[i]
		}

		// 如果删除后最高层没有节点，则减少跳表的层数
		for list.level > 1 && list.head.next[list.level-1] == nil {
			list.level--
		}
		fmt.Printf("Deleted: %d\n", value)
	} else {
		fmt.Printf("Value not found: %d\n", value)
	}
}

// Display 打印跳表的每一层
func (list *SkipList) Display() {
	for i := 0; i < list.level; i++ {
		fmt.Printf("Level %d: ", i)
		node := list.head.next[i]
		// 遍历每一层的节点并打印
		for node != nil {
			fmt.Printf("%d -> ", node.value)
			node = node.next[i]
		}
		fmt.Println("nil")
	}
}

func main() {
	rand.Seed(time.Now().UnixNano()) // 设置随机种子

	skipList := NewSkipList() // 创建跳表实例

	// 插入一些值
	skipList.Insert(3)
	skipList.Insert(6)
	skipList.Insert(7)
	skipList.Insert(9)
	skipList.Insert(12)
	skipList.Insert(19)
	skipList.Insert(17)
	skipList.Insert(26)
	skipList.Insert(21)
	skipList.Insert(25)

	skipList.Display() // 打印跳表

	// 搜索一些值
	fmt.Println("Search for 19:", skipList.Search(19))
	fmt.Println("Search for 4:", skipList.Search(4))

	// 删除一些值
	skipList.Delete(19)
	skipList.Delete(4)

	skipList.Display() // 打印跳表
}

// 在这里我们要将构建成的跳表理解成一个竖着放的数组
/*
         1    2      3     4    5     6    7   8   9   10  11  12  13 
Level 3: 3 -> 12 -> 26 -> nil
Level 2: 3 -> 6 -> 12 -> 19 -> 26 -> nil
Level 1: 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26 -> nil
Level 0: 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26 -> nil

1，2，3，4代表数组1，2，3，4
假如寻找19
我们查找的时候在level 3 中找到小于索引的最大数字
找到了26
现在相当于都到了3这个位置
到下一层也是3，他的3是 12，往下找19
19是4，再往下一层的4
以此类推
*/